package com.hy.study.practice.search;

import java.util.Arrays;

/**
 * 斐波拉契数列查找算法（黄金分割查找）0.618
 * 元素也必须是有序的
 * 斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
 * <p>
 * 斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
 * 斐波那契查找的时间复杂度还是O(log 2 n )，但是 与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。
 * 对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。
 */
public class FibSearch {
    private static int maxSize = 20;

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(arr));
        int i = fibSearch(arr, 10);
        System.out.println(i);
    }

    private static int fibSearch(int arr[], int value) {
        //1.初始化有个斐波拉契数列
        int f[] = fib();
        int maxLength = arr.length;
        int maxIndex = 0;//斐波拉契中最大得值
        int k = 0;

        //2.在斐波拉契数列表中找到一个比 当前数组长度稍大的数
        for (int i = 0; i < f.length; i++) {
            if (f[i] > maxLength) {
                maxIndex = f[i];
                k = i+1;
                break;
            }
        }
        //2.扩展数组 并将数组的后面位用最后一个值填充
        arr = Arrays.copyOf(arr, maxIndex);
        for (int i = maxLength; i < maxIndex; i++) {
            arr[i] = arr[maxLength-1];
        }
        int left = 0;
        int right = arr.length - 1;
        //3.开始查找 从 f(n-1) 和 f(n-2)开始递归
        while (left <= right) {
            int mid = left + f[k - 1] - 1;//减一 是为了迎合 数组下标从0开始
            int midValue = arr[mid];
            if (value < midValue) {
                //向左边找
                right = mid - 1;
                k -= 1;
            } else if (value > midValue) {
                //向右边找
                left = mid + 1;
                k -= 2;
            } else {
                //找到了
                if (mid < maxLength - 1) {
                    return mid;
                } else {
                    return maxLength - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 得到一个斐波拉契数列
     * 1 1 2 3 5 8 13 21 34 55 89
     *
     * @return
     */
    private static int[] fib() {
        int arr[] = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }


}
